﻿#define _CRT_SECURE_NO_WARNINGS 1
//class Solution {
//public:
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param arr int整型vector the array
//     * @return int整型
//     */
//    int maxLength(vector<int>& arr) {
//        if (arr.size() == 0)
//            return 0;
//        vector<int> v;
//        v.push_back(arr[0]);
//        for (int i = 1; i < arr.size(); i++) {
//            int j = 0;
//            while (j < v.size())
//            {
//                if (arr[i] == v[j])
//                {
//                    break;
//                }
//                j++;
//            }
//            if (j == v.size())
//                v.push_back(arr[i]);
//        }
//
//        return v.size();
//    }
//};


//class Solution {
//public:
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param arr int整型vector the array
//     * @return int整型
//     */
//    int maxLength(vector<int>& arr) {
//        vector<vector<int>> vv;
//        vector<int> v;
//        int maxlength = 1;
//        v.push_back(arr[0]);
//        for (int i = 1; i < arr.size(); i++)
//        {
//            int j = 0;
//            while (j < v.size())
//            {
//                if (v[j] == arr[i])
//                {
//                    vv.push_back(v);
//                    v.clear();
//                    break;
//                }
//                j++;
//            }
//            v.push_back(arr[i]);
//        }
//        if (!v.empty())
//        {
//            vv.push_back(v);
//        }
//        for (int i = 0; i < vv.size(); i++)
//        {
//            if (vv[i].size() > maxlength)
//            {
//                maxlength = vv[i].size();
//            }
//        }
//        return maxlength;
//    }
//};


//#include <iostream>
//#include <string>
//using namespace std;
//
//int main()
//{
//    int T;
//    cin >> T;
//    for (int i = 0; i < T; i++)
//    {
//        int n = 0, k = 0;
//        string s;
//        cin >> n >> k;
//        cin >> s;
//        int count = 0;
//        int vectory = 0;
//        for (int j = 0; j < s.size(); j++)
//        {
//            if (j != 0 && s[j] == 'W' && s[j - 1] == 'W')
//            {
//                vectory++;
//            }
//            else if (s[j] == 'W')
//            {
//                vectory = 1;
//            }
//            else if (s[j] == 'L')
//            {
//                vectory = 0;
//            }
//
//            if (vectory >= 3)
//            {
//                count += k;
//            }
//            else if (vectory > 0)
//            {
//                count++;
//            }
//            else if (vectory == 0)
//            {
//                count--;
//            }
//        }
//        cout << count << endl;
//    }
//    return 0;
//}


//#include <iostream>
//#include <cstring>
//using namespace std;
//
//int main()
//{
//    char str[1024];
//    char s[1024];
//    char ss[1024];
//    int k = 0;
//    fgets(str, 1023, stdin);
//    fgets(s, 1023, stdin);
//    str[strlen(str) - 1] = '\0';
//    s[strlen(s) - 1] = '\0';
//    for (int i = 0; i < strlen(str); i++)
//    {
//        int j = 0;
//        while (j < strlen(s))
//        {
//            if (s[j] == str[i])
//            {
//                break;
//            }
//            j++;
//        }
//        if (j >= strlen(s))
//        {
//            ss[k++] = str[i];
//        }
//    }
//    ss[k] = '\0';
//    fputs(ss, stdout);
//    return 0;
//}


//#include <iostream>
//#include <cstring>
//using namespace std;
//
//int main()
//{
//    char str[1024];
//    char s[1024];
//    char ss[1024];
//    int k = 0;
//    fgets(str, 101, stdin);
//    fgets(s, 101, stdin);
//    str[strlen(str) - 1] = '\0';
//    s[strlen(s) - 1] = '\0';
//    for (int i = 0; i < strlen(str); i++)
//    {
//        int j = 0;
//        while (j < strlen(s))
//        {
//            if (s[j] == str[i])
//            {
//                break;
//            }
//            j++;
//        }
//        if (j >= strlen(s))
//        {
//            ss[k++] = str[i];
//        }
//    }
//    ss[k] = '\0';
//    fputs(ss, stdout);
//
//    return 0;
//}



//#include <iostream>
//#include <string>
//using namespace std;
//
//int main()
//{
//    int n = 0;
//    cin >> n;
//    string s;
//    int count = 0;
//    cin >> s;
//    for (int i = 0; i < s.size(); i++)
//    {
//        if (s[i] == 's')
//        {
//            for (int j = 0; j < s.size(); j++)
//            {
//                if (s[j] == 'h')
//                {
//                    for (int k = 0; k < s.size(); k++)
//                    {
//                        if (s[k] == 'y')
//                        {
//                            count++;
//                        }
//                    }
//                }
//            }
//        }
//    }
//    cout << count << endl;
//    return 0;
//}


//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main()
//{
//    int n = 0, mony = 0;
//    cin >> n;
//    vector<int> v(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v[i];
//    }
//    int max = 0, min = 10000;
//    int left = 0, right = n - 1;
//    while (right >= left)
//    {
//        if (v[left] < min)
//        {
//            min = v[left];
//        }
//        if (v[right] > max)
//        {
//            max = v[right];
//        }
//        right--;
//        left++;
//    }
//    if (max - min > 0)
//    {
//        mony = max - min;
//    }
//    cout << mony << endl;
//    return 0;
//}


//#include <iostream>
//#include <vector>
//using namespace std;
//int main()
//{
//    int n = 0, mony = 0;
//    cin >> n;
//    vector<int> v(n);  
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v[i];
//    }
//    for (int i = 0; i < n - 1; i++)
//    {
//        int min = v[i], max = v[i + 1];
//        for (int j = i + 1; j < n; j++)
//        {
//            if (v[j] > max)
//            {
//                max = v[j];
//            }
//        }
//        if (max - min > mony)
//        {
//            mony = max - min;
//        }
//    }
//    cout << mony << endl;
//    return 0;
//}


//#include <iostream>
//using namespace std;
//
//int main()
//{
//    long long n = 0, m = 0, a = 0, b = 0;
//    long long mony = 0;
//    cin >> n >> m >> a >> b;
//    if (a > b)
//    {
//        while (n - 2 >= 0 && m - 1 >= 0)
//        {
//            n -= 2;
//            m -= 1;
//            mony += a;
//        }
//    }
//    else
//    {
//        while (n - 1 >= 0 && m - 2 >= 0)
//        {
//            n -= 1;
//            m -= 2;
//            mony += b;
//        }
//    }
//    if (n == 1 && m >= 2)
//    {
//        mony += b;
//        n -= 1;
//        m -= 2;
//    }
//    if (n >= 2 && m == 1)
//    {
//        mony += a;
//        n -= 2;
//        m -= 1;
//    }
//    cout << mony << endl;
//    return 0;
//}


//#include <iostream>
//using namespace std;
//
//int main()
//{
//    long long n = 0, m = 0, n2 = 0, m2 = 0, a = 0, b = 0;
//    long long mony1 = 0, mony2 = 0;
//    cin >> n >> m >> a >> b;
//    n2 = n, m2 = m;
//    while (n - 2 >= 0 && m - 1 >= 0)
//    {
//        n -= 2;
//        m -= 1;
//        mony1 += a;
//    }
//    if (n == 1 && m >= 2)
//    {
//        mony1 += b;
//        n -= 1;
//        m -= 2;
//    }
//    while (n2 - 1 >= 0 && m2 - 2 >= 0)
//    {
//        n2 -= 1;
//        m2 -= 2;
//        mony2 += b;
//    }
//    if (n2 >= 2 && m2 == 1)
//    {
//        mony2 += a;
//        n2 -= 2;
//        m2 -= 1;
//    }
//    long long mony = max(mony1, mony2);
//    cout << mony << endl;
//    return 0;
//}


//#include <iostream>
//#include <cstring>
//using namespace std;
//
//int main()
//{
//    char s[101];
//    fgets(s, 100, stdin);
//    char str[101];
//    s[strlen(s) - 1] = '\0';
//    int k = 0;
//    for (int i = strlen(s) - 1; i >= 0; i--)
//    {
//        if (s[i] == ' ')
//        {
//            int j = i + 1;
//            while (j < strlen(s) && s[j] != ' ')
//            {
//                str[k++] = s[j++];
//            }
//            str[k++] = ' ';
//        }
//    }
//    if (s[0] != ' ')
//    {
//        int i = 0;
//        while (i < strlen(s) && s[i] != ' ')
//        {
//            str[k++] = s[i++];
//        }
//    }
//    str[k] = '\0';
//    fputs(str, stdout);
//    return 0;
//}


//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main()
//{
//    int n = 0;
//    cin >> n;
//    vector<int> v(n + 1);
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> v[i];
//    }
//    int buy = -v[1];
//    int mony = 0;
//    for (int i = 2; i <= n; i++)
//    {
//        if (mony - v[i] > buy)
//        {
//            buy = mony - v[i];
//        }
//        if (buy + v[i] > mony)
//        {
//            mony = buy + v[i];
//        }
//    }
//    cout << mony << endl;
//    return 0;
//}
